package avlTree;

public class AVLTree {
    static class TreeNode{
        public int val;
        public int bf;//当前节点的平衡因子=右子树高度-左子树高度
        public TreeNode left;
        public TreeNode right;
        public TreeNode parent;
        public TreeNode(int val){
            this.val = val;
        }
    }
    public TreeNode root;//根节点

    public boolean insert(int val){
        TreeNode node = new TreeNode(val);
        if(root == null){
            root = node;
            return true;
        }

        TreeNode parent = null;
        TreeNode cur = root;
        while(cur != null){
            if(cur.val<val){
                parent = cur;
                cur = cur.right;
            }else if(cur.val>val){
                parent = cur;
                cur = cur.left;
            }else {
                return false;
            }
        }
        //cur ==null
        if(parent.val<val){
            parent.right = node;
        }else {
            parent.left = node;
        }

        node.parent = parent;
        cur = node;

        //平衡因子的修改
        while (parent!=null){
            if(cur == parent.right){
                parent.bf++;
            }else {
                parent.bf--;
            }

            //检查当前的平衡因子 是不是 1 0 -1
            if(parent.bf==0){
                break;
            } else if (parent.bf==1||parent.bf==-1) {
                cur=parent;
                parent = cur.parent;
            } else {
                if(parent.bf ==2){//右树高->需要降低右树的高度
                    if(cur.bf==1){
                        rotateLeft(parent);
                    }else {
                        //cur.bf== -1
                        rotateRL(parent);
                    }

                }else {
                    //parent.bf == -2 左树高->需要降低左树的高度
                    if(cur.bf==-1){
                        rotateRight(parent);
                    }else {
                        //cur.bf== 1
                        rotateLR(parent);
                    }
                }
                break;
            }
        }
        return true;

    }

    //左单旋
    private void rotateLeft(TreeNode parent){
        TreeNode subR = parent.right;
        TreeNode subRL = subR.left;
        parent.right = subRL;
        subR.left = parent;//这句和上句代码位置不能交换，有先后顺序
        if(subRL!=null){
            subRL.parent=parent;
        }
        TreeNode pParent = parent.parent;
        parent.parent = subR;
        if(root == parent){
            root=subR;
            root.parent=null;
        }else {
            if(pParent.left==parent){
                pParent.left =subR;
            }else {
                pParent.right=subR;
            }
            subR.parent=pParent;
        }
        subR.bf = parent.bf = 0;

    }

    //右单旋
    private void rotateRight(TreeNode parent){
        TreeNode subL = parent.left;
        TreeNode subLR = subL.right;
        parent.left = subLR;
        subL.right=parent;
        //判断是否存在subLR
        if(subLR!=null){
            subLR.parent=parent;
        }
        //必须先记录
        TreeNode pParent = parent.parent;
        parent.parent=subL;
        //检查 当前parent是不是根节点
        if(root==parent){
            root = subL;
            root.parent=null;
        }else {
            //不是根节点的话，判断这棵子树是左子树还是右子树
            if(pParent.left==parent){
                pParent.left=subL;
            }else {
                pParent.right=subL;
            }
            subL.parent=pParent;
        }
        subL.bf=parent.bf=0;

    }

    //右左双旋
    private void rotateLR(TreeNode parent){
        TreeNode subL = parent.left;
        TreeNode subLR = subL.right;
        int bf = subLR.bf;

        rotateLeft(parent.left);
        rotateRight(parent);

        if(bf == -1) {
            subL.bf = 0;
            subLR.bf = 0;
            parent.bf = 1;
        }else if(bf == 1){
            subL.bf = -1;
            subLR.bf = 0;
            parent.bf = 0;
        }
    }

    //右左双旋
    private void rotateRL(TreeNode parent){
        TreeNode subR = parent.right;
        TreeNode subRL = subR.left;
        int bf = subRL.bf;

        rotateRight(parent.right);
        rotateLeft(parent);

        if(bf == 1) {
            parent.bf = -1;
            subR.bf = 0;
            subRL.bf = 0;
        }else if(bf == -1){
            parent.bf = 0;
            subR.bf = 1;
            subRL.bf = 0;
        }
    }

    //中序遍历的结果是有序的 就能说明当前树 一定是AVL树吗？  不一定的
    public void inorder(TreeNode root) {
        if(root == null) return;
        inorder(root.left);
        System.out.print(root.val+"  ");
        inorder(root.right);
    }

    private int height(TreeNode root) {
        if(root == null) return 0;
        int leftH = height(root.left);
        int rightH = height(root.right);

        return leftH > rightH ? leftH+1 : rightH+1;
    }

    public boolean isBalanced(TreeNode root) {
        if(root == null) return true;
        int leftH = height(root.left);
        int rightH = height(root.right);

        if(rightH-leftH != root.bf) {
            System.out.println("这个节点："+root.val+" 平衡因子异常");
            return false;
        }

        return Math.abs(leftH-rightH) <= 1
                && isBalanced(root.left)
                && isBalanced(root.right);
    }

}
